package one.chapter_2;

/**
 * 希尔排序
 * 思想：基于插入排序 ，插入排序只能左右相邻的元素比较，
 * 而希尔排序将数组中间隔h长度的两个元素进行比较。从而是一些较小的元素直接排到比较靠前的地方
 */
public class ShellSort extends AbstractSort {

    protected void sort(Comparable[] a) {
        int N=a.length;

        int h=1;
        while (h<N/3){
            h=3*h+1;
        }

        while (h>=1){
            for (int i=h;i<N;i++){
                for (int j=i;j>=h && less(a[j],a[j-h]);j-=h){
                    exch(a,j,j-h);
                }
            }

            h=h/3;
        }
    }
}
